{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基本概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 术语解释\n",
    "有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度，我这里先简单解释一下：\n",
    "\n",
    "1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。\n",
    "\n",
    "2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。\n",
    "\n",
    "3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。\n",
    "\n",
    "4、非原地排序：需要利用额外的数组来辅助排序。\n",
    "\n",
    "5、时间复杂度：一个算法执行所消耗的时间。\n",
    "\n",
    "6、空间复杂度：运行完一个算法所需的内存大小。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 十大排序\n",
    "\n",
    "为了方便大家查找，我这里弄一个伪目录。\n",
    "- 冒泡排序\n",
    "- 选择排序\n",
    "- 插入排序\n",
    "    - 直接插入排序\n",
    "    - 折半插入排序\n",
    "- 希尔排序\n",
    "- 归并排序\n",
    "- 快速排序\n",
    "- 堆排序\n",
    "- 计数排序\n",
    "- 桶排序\n",
    "- 基数排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**注意：下述代码只是基本原理实现代码，未考虑一些异常场景(比如列表长度==1，原序列是有序数列等等情况)，实际使用时需要多做考虑。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 冒泡排序\n",
    "- **排序原理**：将第i个元素与i+1个相比较，如果list(i)>list(i+1)则互换位置继续后续对比，直至最后。\n",
    "- 稳定排序\n",
    "- 原地排序\n",
    "- 时间复杂度：$O(n^2)$\n",
    "- 空间复杂度：$O(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T02:06:22.505279Z",
     "iopub.status.busy": "2020-08-09T02:06:22.501309Z",
     "iopub.status.idle": "2020-08-09T02:06:22.538719Z",
     "shell.execute_reply": "2020-08-09T02:06:22.534731Z",
     "shell.execute_reply.started": "2020-08-09T02:06:22.505279Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [1, 57, 23, 32, 23, 13, 28, 82, 68, 29, 14, 93, 72, 43, 89, 66, 76, 76, 25, 78, 80, 61, 22, 98, 66, 15, 87, 37, 7, 83]\n",
      "after: [1, 7, 13, 14, 15, 22, 23, 23, 25, 28, 29, 32, 37, 43, 57, 61, 66, 66, 68, 72, 76, 76, 78, 80, 82, 83, 87, 89, 93, 98]\n"
     ]
    }
   ],
   "source": [
    "# 生成乱序列表\n",
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "# 冒泡排序\n",
    "for i in range(len(disorder_list)):\n",
    "    for j in range(len(disorder_list)-i-1):\n",
    "        if disorder_list[j] > disorder_list[j+1]:\n",
    "            disorder_list[j],disorder_list[j+1] = disorder_list[j+1],disorder_list[j]\n",
    "            \n",
    "print('after:',disorder_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-10T08:00:06.542489Z",
     "iopub.status.busy": "2020-08-10T08:00:06.542489Z",
     "iopub.status.idle": "2020-08-10T08:00:07.936205Z",
     "shell.execute_reply": "2020-08-10T08:00:07.934211Z",
     "shell.execute_reply.started": "2020-08-10T08:00:06.542489Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "b5b4f164e45d4162bc467c7f6e0a32ff",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 动画展示\n",
    "from matplotlib import pyplot as plt\n",
    "import matplotlib.animation as animation\n",
    "import numpy as np\n",
    "import random\n",
    "%matplotlib widget\n",
    "color_original = '#ff9999'\n",
    "color_sorted = '#9999ff'\n",
    "color_selected = '#99ff99'\n",
    "\n",
    "def data_gen_bubble_sort(data_to_be_sorted):\n",
    "    for i in range(len(data_to_be_sorted)):\n",
    "        for j in range(0, len(data_to_be_sorted)-i-1):\n",
    "            if data_to_be_sorted[j] > data_to_be_sorted[j+1]:\n",
    "                # exchange the corresponding data\n",
    "                data_to_be_sorted[j], data_to_be_sorted[j+1] = data_to_be_sorted[j+1], data_to_be_sorted[j]\n",
    "            lines[j].set_color(color_original)\n",
    "            lines[j+1].set_color(color_selected)\n",
    "            yield data_to_be_sorted\n",
    "        lines[len(data_to_be_sorted)-i-1].set_color(color_sorted)\n",
    "        yield data_to_be_sorted\n",
    "\n",
    "def update(data):\n",
    "    \"\"\"\n",
    "    这里面获取到的data来自 data_gen返回的数据\n",
    "    \"\"\"\n",
    "    for i in range(len(data)):\n",
    "        lines[i].set_ydata([0, data[i]])\n",
    "    return lines\n",
    "\n",
    "\n",
    "num = 20\n",
    "max_val = 50\n",
    "data_to_be_sorted = np.random.rand(num)*max_val\n",
    "fig, ax = plt.subplots()\n",
    "xdata = [[i+1 for i in range(num)], [i+1 for i in range(num)]]\n",
    "ydata = [[0 for i in range(num)], data_to_be_sorted]\n",
    "lines = ax.plot(xdata, ydata, lw=10, c=color_original)\n",
    "ani = animation.FuncAnimation(fig, update, data_gen_bubble_sort(data_to_be_sorted), interval=num*num)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 选择排序\n",
    "- **排序原理**：首先在列表中找到最小的元素，然后将之与第一个互换，依此类推。\n",
    "- 稳定排序\n",
    "- 原地排序\n",
    "- 时间复杂度：$O(n^2)$\n",
    "- 空间复杂度：$O(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T02:14:04.388679Z",
     "iopub.status.busy": "2020-08-09T02:14:04.386684Z",
     "iopub.status.idle": "2020-08-09T02:14:04.402906Z",
     "shell.execute_reply": "2020-08-09T02:14:04.399844Z",
     "shell.execute_reply.started": "2020-08-09T02:14:04.388679Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [59, 23, 50, 65, 47, 10, 36, 74, 74, 68, 24, 81, 19, 1, 28, 23, 96, 60, 29, 78, 52, 1, 19, 30, 19, 8, 54, 40, 40, 21]\n",
      "after: [1, 1, 8, 10, 19, 19, 19, 21, 23, 23, 24, 28, 29, 30, 36, 40, 40, 47, 50, 52, 54, 59, 60, 65, 68, 74, 74, 78, 81, 96]\n"
     ]
    }
   ],
   "source": [
    "# 生成乱序列表\n",
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "# 选择排序\n",
    "for i in range(len(disorder_list)):\n",
    "    for j in range(i+1, len(disorder_list)):\n",
    "        if disorder_list[j] < disorder_list[i]:\n",
    "            disorder_list[j],disorder_list[i] = disorder_list[i],disorder_list[j]\n",
    "            \n",
    "print('after:',disorder_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-10T08:01:48.936877Z",
     "iopub.status.busy": "2020-08-10T08:01:48.936877Z",
     "iopub.status.idle": "2020-08-10T08:01:48.978862Z",
     "shell.execute_reply": "2020-08-10T08:01:48.977863Z",
     "shell.execute_reply.started": "2020-08-10T08:01:48.936877Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "6486fdfd8584446daf004b4d3f41a05e",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 动画展示\n",
    "from matplotlib import pyplot as plt\n",
    "import matplotlib.animation as animation\n",
    "import numpy as np\n",
    "import random\n",
    "%matplotlib widget\n",
    "color_original = '#ff9999'\n",
    "color_sorted = '#9999ff'\n",
    "color_selected = '#99ff99'\n",
    "\n",
    "def data_gen_bubble_sort(data_to_be_sorted):\n",
    "    for i in range(len(data_to_be_sorted)):\n",
    "        for j in range(i+1, len(data_to_be_sorted)):\n",
    "            if data_to_be_sorted[j] < data_to_be_sorted[i]:\n",
    "                data_to_be_sorted[j],data_to_be_sorted[i] = data_to_be_sorted[i],data_to_be_sorted[j]\n",
    "            lines[j-1].set_color(color_original)\n",
    "            lines[j].set_color(color_selected)\n",
    "            yield data_to_be_sorted\n",
    "        lines[i].set_color(color_sorted)\n",
    "        yield data_to_be_sorted\n",
    "\n",
    "def update(data):\n",
    "    \"\"\"\n",
    "    这里面获取到的data来自 data_gen返回的数据\n",
    "    \"\"\"\n",
    "    for i in range(len(data)):\n",
    "        lines[i].set_ydata([0, data[i]])\n",
    "    return lines\n",
    "\n",
    "\n",
    "num = 10\n",
    "max_val = 50\n",
    "data_to_be_sorted = np.random.rand(num)*max_val\n",
    "fig, ax = plt.subplots()\n",
    "xdata = [[i+1 for i in range(num)], [i+1 for i in range(num)]]\n",
    "ydata = [[0 for i in range(num)], data_to_be_sorted]\n",
    "lines = ax.plot(xdata, ydata, lw=10, c=color_original)\n",
    "ani = animation.FuncAnimation(fig, update, data_gen_bubble_sort(data_to_be_sorted), interval=num*num)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 插入排序\n",
    "- **排序原理**：由前向后排序，判断有序列表后第一个元素与之前元素的大小，直到找到其位置，插入进去，依此类推。\n",
    "- 稳定排序\n",
    "- 原地排序\n",
    "- 时间复杂度：$O(n^2)$\n",
    "- 空间复杂度：$O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 直接插入排序\n",
    "\n",
    "直接插入排序通过顺序查找的方式确定元素位置；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T03:14:50.498821Z",
     "iopub.status.busy": "2020-08-09T03:14:50.497823Z",
     "iopub.status.idle": "2020-08-09T03:14:50.509070Z",
     "shell.execute_reply": "2020-08-09T03:14:50.508104Z",
     "shell.execute_reply.started": "2020-08-09T03:14:50.498821Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [60, 6, 17, 76, 20, 31, 84, 27, 22, 54, 8, 71, 85, 38, 55, 82, 4, 19, 40, 20, 8, 79, 9, 70, 66, 50, 16, 50, 12, 25]\n",
      "[4, 6, 8, 8, 9, 12, 16, 17, 19, 20, 20, 22, 25, 27, 31, 38, 40, 50, 50, 54, 55, 60, 66, 70, 71, 76, 79, 82, 84, 85]\n"
     ]
    }
   ],
   "source": [
    "# 生成乱序列表\n",
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "def InsertSort(myList):\n",
    "     #获取列表长度\n",
    "    length = len(myList)\n",
    "\n",
    "    for i in range(1,length):\n",
    "        #设置当前值前一个元素的标识\n",
    "        j = i - 1\n",
    "\n",
    "        #如果当前值小于前一个元素,则将当前值作为一个临时变量存储,将前一个元素后移一位\n",
    "        if(myList[i] < myList[j]):\n",
    "            temp = myList[i]\n",
    "            myList[i] = myList[j]\n",
    "\n",
    "            #继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素\n",
    "            j = j-1\n",
    "            while j>=0 and myList[j] > temp:\n",
    "                myList[j+1] = myList[j]\n",
    "                j = j-1\n",
    "            #将临时变量赋值给合适位置\n",
    "            myList[j+1] = temp\n",
    "\n",
    "InsertSort(disorder_list)\n",
    "print(disorder_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 折半插入排序\n",
    "折半插入排序通过二分查找的方式确定元素位置；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T04:32:40.016676Z",
     "iopub.status.busy": "2020-08-09T04:32:40.016676Z",
     "iopub.status.idle": "2020-08-09T04:32:40.029640Z",
     "shell.execute_reply": "2020-08-09T04:32:40.028642Z",
     "shell.execute_reply.started": "2020-08-09T04:32:40.016676Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [19, 31, 35, 81, 95, 81, 14, 15, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[19, 31, 35, 81, 95, 81, 14, 15, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[19, 31, 35, 81, 95, 81, 14, 15, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[19, 31, 35, 81, 95, 81, 14, 15, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[19, 31, 35, 81, 95, 81, 14, 15, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[19, 31, 35, 81, 81, 95, 14, 15, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 19, 31, 35, 81, 81, 95, 15, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 19, 31, 35, 81, 81, 95, 65, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 19, 31, 35, 65, 81, 81, 95, 88, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 19, 31, 35, 65, 81, 81, 88, 95, 26, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 19, 26, 31, 35, 65, 81, 81, 88, 95, 81, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 19, 26, 31, 35, 65, 81, 81, 81, 88, 95, 64, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 19, 26, 31, 35, 64, 65, 81, 81, 81, 88, 95, 16, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 16, 19, 26, 31, 35, 64, 65, 81, 81, 81, 88, 95, 27, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 16, 19, 26, 27, 31, 35, 64, 65, 81, 81, 81, 88, 95, 15, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 19, 26, 27, 31, 35, 64, 65, 81, 81, 81, 88, 95, 94, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 19, 26, 27, 31, 35, 64, 65, 81, 81, 81, 88, 94, 95, 64, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 19, 26, 27, 31, 35, 64, 64, 65, 81, 81, 81, 88, 94, 95, 81, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 19, 26, 27, 31, 35, 64, 64, 65, 81, 81, 81, 81, 88, 94, 95, 62, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 19, 26, 27, 31, 35, 62, 64, 64, 65, 81, 81, 81, 81, 88, 94, 95, 90, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 19, 26, 27, 31, 35, 62, 64, 64, 65, 81, 81, 81, 81, 88, 90, 94, 95, 91, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 19, 26, 27, 31, 35, 62, 64, 64, 65, 81, 81, 81, 81, 88, 90, 91, 94, 95, 16, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 16, 19, 26, 27, 31, 35, 62, 64, 64, 65, 81, 81, 81, 81, 88, 90, 91, 94, 95, 39, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 16, 19, 26, 27, 31, 35, 39, 62, 64, 64, 65, 81, 81, 81, 81, 88, 90, 91, 94, 95, 67, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 16, 19, 26, 27, 31, 35, 39, 62, 64, 64, 65, 67, 81, 81, 81, 81, 88, 90, 91, 94, 95, 51, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 16, 19, 26, 27, 31, 35, 39, 51, 62, 64, 64, 65, 67, 81, 81, 81, 81, 88, 90, 91, 94, 95, 90, 56, 57, 18]\n",
      "[14, 15, 15, 16, 16, 19, 26, 27, 31, 35, 39, 51, 62, 64, 64, 65, 67, 81, 81, 81, 81, 88, 90, 90, 91, 94, 95, 56, 57, 18]\n",
      "[14, 15, 15, 16, 16, 19, 26, 27, 31, 35, 39, 51, 56, 62, 64, 64, 65, 67, 81, 81, 81, 81, 88, 90, 90, 91, 94, 95, 57, 18]\n",
      "[14, 15, 15, 16, 16, 19, 26, 27, 31, 35, 39, 51, 56, 57, 62, 64, 64, 65, 67, 81, 81, 81, 81, 88, 90, 90, 91, 94, 95, 18]\n",
      "[14, 15, 15, 16, 16, 18, 19, 26, 27, 31, 35, 39, 51, 56, 57, 62, 64, 64, 65, 67, 81, 81, 81, 81, 88, 90, 90, 91, 94, 95]\n"
     ]
    }
   ],
   "source": [
    "# 生成乱序列表\n",
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "#折半排序类  \n",
    "class HalfInsertSort():    \n",
    "    #开始排序  \n",
    "    \n",
    "    #arrData:要排序的数组  \n",
    "    def sort(self, arrData):    \n",
    "        for i in range(1,len(arrData)):  \n",
    "            self.halfSort(arrData,i,0,i-1);  \n",
    "            print(arrData);  \n",
    "        return;    \n",
    "    #折半排序  \n",
    "    #target:要排序的目标的索引值  \n",
    "    #mi:已排序的最小索引  \n",
    "    #ma:已排序的最大索引  \n",
    "    \n",
    "    #target要在[mi,ma]中查找合适的位置  \n",
    "    def halfSort(self,arrData,target,mi,ma):    \n",
    "        i=(mi+ma)//2;#中间索引  \n",
    "        c=arrData[target]-arrData[i];  \n",
    "        if mi==ma or i==ma or i==mi:  \n",
    "            d=arrData[target]-arrData[ma];  \n",
    "            if c>=0 and d<0:  \n",
    "                self.insert(arrData,target,i + 1);  \n",
    "            elif c<0:  \n",
    "                self.insert(arrData,target,i);  \n",
    "            elif d>=0:  \n",
    "                self.insert(arrData,target,ma + 1);  \n",
    "            return;   \n",
    "        if c>0:  \n",
    "            self.halfSort(arrData,target,i+1,ma);  \n",
    "        elif c==0:  \n",
    "            self.insert(arrData,target,i+1);  \n",
    "            return;    \n",
    "        else:  \n",
    "            self.halfSort(arrData,target,mi,i-1);         \n",
    "        return;  \n",
    "    \n",
    "    #将目录插入到dest位置  \n",
    "    def insert(self,arrData,target,dest):    \n",
    "        tmp=arrData[target];  \n",
    "        i = target - 1;  \n",
    "        #将dest身后的已排序的元素向后移动一位  \n",
    "        while i>=dest:  \n",
    "            arrData[i+1]=arrData[i];  \n",
    "            i = i -1;  \n",
    "        arrData[dest]=tmp;    \n",
    "        return;    \n",
    "        \n",
    "sortVal=HalfInsertSort();    \n",
    "sortVal.sort(disorder_list);    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 希尔排序\n",
    "- **排序原理**：数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。\n",
    "- 非稳定排序\n",
    "- 原地排序\n",
    "- 时间复杂度：$O(n*log(n))$\n",
    "- 空间复杂度：$O(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T04:42:05.760897Z",
     "iopub.status.busy": "2020-08-09T04:42:05.759900Z",
     "iopub.status.idle": "2020-08-09T04:42:05.771867Z",
     "shell.execute_reply": "2020-08-09T04:42:05.770904Z",
     "shell.execute_reply.started": "2020-08-09T04:42:05.759900Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [78, 15, 55, 56, 84, 22, 45, 7, 50, 50, 57, 20, 14, 100, 62, 46, 49, 20, 84, 3, 85, 15, 37, 63, 39, 53, 58, 87, 6, 72]\n",
      "after: [3, 6, 7, 14, 15, 15, 20, 20, 22, 37, 39, 45, 46, 49, 50, 50, 53, 55, 56, 57, 58, 62, 63, 72, 78, 84, 84, 85, 87, 100]\n"
     ]
    }
   ],
   "source": [
    "# 生成乱序列表\n",
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "def shellSort(nums):\n",
    "    # 设定步长\n",
    "    step = len(nums)/2\n",
    "    while step > 0:\n",
    "        for i in range(step, len(nums)):\n",
    "            # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置\n",
    "            while i >= step and nums[i-step] > nums[i]:\n",
    "                nums[i], nums[i-step] = nums[i-step], nums[i]\n",
    "                i -= step\n",
    "        step = step/2\n",
    "    return nums\n",
    "shell_sort(disorder_list)\n",
    "print('after:',disorder_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 归并排序\n",
    "- **排序原理**：通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。\n",
    "- 非稳定排序\n",
    "- 非原地排序\n",
    "- 时间复杂度：$O(n*log(n))$\n",
    "- 空间复杂度：$O(n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T04:53:29.986351Z",
     "iopub.status.busy": "2020-08-09T04:53:29.986351Z",
     "iopub.status.idle": "2020-08-09T04:53:29.997323Z",
     "shell.execute_reply": "2020-08-09T04:53:29.996325Z",
     "shell.execute_reply.started": "2020-08-09T04:53:29.986351Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [73, 58, 44, 63, 69, 25, 37, 81, 17, 58, 69, 6, 17, 15, 3, 5, 60, 55, 89, 62, 7, 26, 73, 5, 16, 93, 89, 69, 74, 57]\n",
      "after： [3, 5, 5, 6, 7, 15, 16, 17, 17, 25, 26, 37, 44, 55, 57, 58, 58, 60, 62, 63, 69, 69, 69, 73, 73, 74, 81, 89, 89, 93]\n"
     ]
    }
   ],
   "source": [
    "# 生成乱序列表\n",
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "#归并排序 \n",
    "def merge_sort(alist):\n",
    "    if len(alist) <= 1:\n",
    "        return alist\n",
    "    # 二分分解\n",
    "    num = len(alist) // 2\n",
    "    left = merge_sort(alist[:num])\n",
    "    right = merge_sort(alist[num:])\n",
    "    # 合并\n",
    "    return merge(left, right)\n",
    "  \n",
    "def merge(left, right):\n",
    "    # left与right的下标指针\n",
    "    l, r = 0, 0\n",
    "    result = []\n",
    "    while l < len(left) and r < len(right):\n",
    "        if left[l] < right[r]:\n",
    "            result.append(left[l])\n",
    "            l += 1\n",
    "        else:\n",
    "            result.append(right[r])\n",
    "            r += 1\n",
    "    result += left[l:]\n",
    "    result += right[r:]\n",
    "    return result\n",
    "  \n",
    "sorted_alist = merge_sort(disorder_list)\n",
    "print('after：', sorted_alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 快速排序\n",
    "- **排序原理**：我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。\n",
    "- 非稳定排序\n",
    "- 原地排序\n",
    "- 时间复杂度：$O(n*log(n))$\n",
    "- 空间复杂度：$O(log(n))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T05:06:14.156931Z",
     "iopub.status.busy": "2020-08-09T05:06:14.155933Z",
     "iopub.status.idle": "2020-08-09T05:06:14.167931Z",
     "shell.execute_reply": "2020-08-09T05:06:14.166417Z",
     "shell.execute_reply.started": "2020-08-09T05:06:14.156931Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [5, 15, 16, 12, 74, 15, 75, 14, 9, 41, 30, 87, 10, 30, 51, 57, 38, 14, 74, 64, 14, 62, 44, 64, 29, 34, 70, 21, 95, 5]\n",
      "after:  [5, 5, 9, 10, 12, 14, 14, 14, 15, 15, 16, 21, 29, 30, 30, 34, 38, 41, 44, 51, 57, 62, 64, 64, 70, 74, 74, 75, 87, 95]\n"
     ]
    }
   ],
   "source": [
    "# 生成乱序列表\n",
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "# 实现快排\n",
    "def quick_sort(nums):\n",
    "    if len(nums) <= 1:\n",
    "        return nums\n",
    " \n",
    "    # 左边数组\n",
    "    left = []\n",
    "    # 右边数组\n",
    "    right = []\n",
    "    # 基准数\n",
    "    base = nums.pop()\n",
    "    # 对原数组进行划分\n",
    "    for x in nums:\n",
    "        if x < base:\n",
    "            left.append(x)\n",
    "        else:\n",
    "            right.append(x)\n",
    "    # 递归调用\n",
    "    return quicksort(left) + [base] + quicksort(right)\n",
    " \n",
    "\n",
    "print('after: ', quick_sort(disorder_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Python排序算法（一）——快速排序: https://www.cnblogs.com/pythonbao/p/10768593.html\n",
    "- 快速排序 - python版超详细讲解: https://blog.csdn.net/weixin_43250623/article/details/88931925\n",
    "- 快速排序(python实现): https://blog.csdn.net/weixin_41678663/article/details/81813759"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 堆排序\n",
    "- **排序原理**：堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。\n",
    "- 非稳定排序\n",
    "- 原地排序\n",
    "- 时间复杂度：$O(n*log(n))$\n",
    "- 空间复杂度：$O(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T05:29:05.209364Z",
     "iopub.status.busy": "2020-08-09T05:29:05.208368Z",
     "iopub.status.idle": "2020-08-09T05:29:05.223457Z",
     "shell.execute_reply": "2020-08-09T05:29:05.221879Z",
     "shell.execute_reply.started": "2020-08-09T05:29:05.209364Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [32, 95, 40, 35, 38, 85, 36, 86, 60, 78, 31, 75, 17, 58, 75, 8, 94, 14, 9, 1, 76, 73, 72, 57, 22, 10, 24, 49, 46, 84]\n",
      "[1, 8, 9, 10, 14, 17, 22, 24, 31, 32, 35, 36, 38, 40, 46, 49, 57, 58, 60, 72, 73, 75, 75, 76, 78, 84, 85, 86, 94, 95]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "import random\n",
    "def MAX_Heapify(heap,HeapSize,root):#在堆中做结构调整使得父节点的值大于子节点\n",
    "\n",
    "    left = 2*root + 1\n",
    "    right = left + 1\n",
    "    larger = root\n",
    "    if left < HeapSize and heap[larger] < heap[left]:\n",
    "        larger = left\n",
    "    if right < HeapSize and heap[larger] < heap[right]:\n",
    "        larger = right\n",
    "    if larger != root:#如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作\n",
    "        heap[larger],heap[root] = heap[root],heap[larger]\n",
    "        MAX_Heapify(heap, HeapSize, larger)\n",
    "\n",
    "def Build_MAX_Heap(heap):#构造一个堆，将堆中所有数据重新排序\n",
    "    HeapSize = len(heap)#将堆的长度当独拿出来方便\n",
    "    for i in range((HeapSize -2)//2,-1,-1):#从后往前出数\n",
    "        MAX_Heapify(heap,HeapSize,i)\n",
    "\n",
    "def HeapSort(heap):#将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。\n",
    "    Build_MAX_Heap(heap)\n",
    "    for i in range(len(heap)-1,-1,-1):\n",
    "        heap[0],heap[i] = heap[i],heap[0]\n",
    "        MAX_Heapify(heap, i, 0)\n",
    "    return heap\n",
    "\n",
    "\n",
    "HeapSort(disorder_list)\n",
    "print( disorder_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- PYTHON实现堆排序: https://www.cnblogs.com/NewsunLs/p/9568126.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 计数排序\n",
    "- **排序原理**：：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。  \n",
    "计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。当数值中有非整数时，计数数组的索引无法分配.\n",
    "- 稳定排序\n",
    "- 非原地排序\n",
    "- 时间复杂度：$O(n+k)$\n",
    "- 空间复杂度：$O(k)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T05:36:44.412348Z",
     "iopub.status.busy": "2020-08-09T05:36:44.412348Z",
     "iopub.status.idle": "2020-08-09T05:36:44.421915Z",
     "shell.execute_reply": "2020-08-09T05:36:44.420380Z",
     "shell.execute_reply.started": "2020-08-09T05:36:44.412348Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [53, 13, 53, 60, 73, 8, 95, 74, 96, 66, 21, 8, 36, 43, 60, 46, 30, 53, 84, 96, 71, 17, 54, 66, 100, 66, 30, 85, 87, 93]\n",
      "after:  [8, 8, 13, 17, 21, 30, 30, 36, 43, 46, 53, 53, 53, 54, 60, 60, 66, 66, 66, 71, 73, 74, 84, 85, 87, 93, 95, 96, 96, 100]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "def count_sort(l):\n",
    "    n = len(l)\n",
    "    res = [None] * n\n",
    "    # 首次循环遍历, 每个列表的数都统计\n",
    "    for i in range(n):\n",
    "        # p 表示 a[i] 大于列表其他数 的次数\n",
    "        p = 0\n",
    "        # q 表示 等于 a[i] 的次数\n",
    "        q = 0\n",
    "        # 二次循环遍历, 列表中的每个数都和首次循环的数比较\n",
    "        for j in range(n):\n",
    "            if l[i] > l[j]:\n",
    "                p += 1\n",
    "            elif l[i] == l[j]:\n",
    "                q += 1\n",
    "        for k in range(p, p+q):  # q表示 相等的次数,就表示, 从 P 开始索引后, 连续 q 次,都是同样的 数\n",
    "            res[k] = l[i]\n",
    "    return res\n",
    "\n",
    "print('after: ', count_sort(disorder_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 计数排序与桶排序python实现: https://www.cnblogs.com/sfencs-hcy/p/10612422.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 桶排序\n",
    "- **排序原理**：桶排序就是把最大值和最小值之间的数进行瓜分，例如分成n个区间，n个区间对应n个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。之后每个桶里面的数据就是有序的了，我们在进行合并汇总。\n",
    "- 稳定排序\n",
    "- 非原地排序\n",
    "- 时间复杂度：$O(n+k)$\n",
    "- 空间复杂度：$O(n+k)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T05:41:29.958294Z",
     "iopub.status.busy": "2020-08-09T05:41:29.957297Z",
     "iopub.status.idle": "2020-08-09T05:41:29.973254Z",
     "shell.execute_reply": "2020-08-09T05:41:29.971259Z",
     "shell.execute_reply.started": "2020-08-09T05:41:29.958294Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [72, 81, 27, 48, 39, 40, 99, 57, 87, 10, 98, 39, 53, 89, 13, 47, 25, 4, 51, 1, 89, 89, 73, 84, 27, 53, 13, 74, 36, 96]\n",
      "after:  [1, 4, 10, 13, 13, 25, 27, 27, 36, 39, 39, 40, 47, 48, 51, 53, 53, 57, 72, 73, 74, 81, 84, 87, 89, 89, 89, 96, 98, 99]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "def bucket_sort(s):\n",
    "    \"\"\"桶排序\"\"\"\n",
    "    min_num = min(s)\n",
    "    max_num = max(s)\n",
    "    # 桶的大小\n",
    "    bucket_range = (max_num-min_num) / len(s)\n",
    "    # 桶数组\n",
    "    count_list = [ [] for i in range(len(s) + 1)]\n",
    "    # 向桶数组填数\n",
    "    for i in s:\n",
    "        count_list[int((i-min_num)//bucket_range)].append(i)\n",
    "    s.clear()\n",
    "    # 回填，这里桶内部排序直接调用了sorted\n",
    "    for i in count_list:\n",
    "        for j in sorted(i):\n",
    "            s.append(j)\n",
    "\n",
    "bucket_sort(disorder_list) \n",
    "print('after: ',disorder_list) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基数排序\n",
    "- **排序原理**：先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小……\n",
    "- 稳定排序\n",
    "- 非原地排序\n",
    "- 时间复杂度：$O(kn)$\n",
    "- 空间复杂度：$O(n+k)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-09T05:47:53.583495Z",
     "iopub.status.busy": "2020-08-09T05:47:53.582498Z",
     "iopub.status.idle": "2020-08-09T05:47:53.594032Z",
     "shell.execute_reply": "2020-08-09T05:47:53.592470Z",
     "shell.execute_reply.started": "2020-08-09T05:47:53.583495Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before: [37, 46, 98, 43, 94, 99, 90, 38, 93, 42, 79, 93, 78, 67, 39, 42, 48, 99, 20, 8, 46, 98, 19, 97, 58, 62, 15, 10, 78, 37]\n",
      "bucket_list:  [[90, 20, 10], [], [42, 42, 62], [43, 93, 93], [94], [15], [46, 46], [37, 67, 97, 37], [98, 38, 78, 48, 8, 98, 58, 78], [99, 79, 39, 99, 19]]\n",
      "bucket_list:  [[8], [10, 15, 19], [20], [37, 37, 38, 39], [42, 42, 43, 46, 46, 48], [58], [62, 67], [78, 78, 79], [], [90, 93, 93, 94, 97, 98, 98, 99, 99]]\n",
      "after: [8, 10, 15, 19, 20, 37, 37, 38, 39, 42, 42, 43, 46, 46, 48, 58, 62, 67, 78, 78, 79, 90, 93, 93, 94, 97, 98, 98, 99, 99]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "disorder_list = [random.randint(1,100) for i in range(30)]\n",
    "print('before:',disorder_list)\n",
    "\n",
    "def radix_sort(s):\n",
    "    \"\"\"基数排序\"\"\"\n",
    "    i = 0 # 记录当前正在排拿一位，最低位为1\n",
    "    max_num = max(s)  # 最大值\n",
    "    j = len(str(max_num))  # 记录最大值的位数\n",
    "    while i < j:\n",
    "        bucket_list =[[] for _ in range(10)] #初始化桶数组\n",
    "        for x in s:\n",
    "            bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组\n",
    "        print('bucket_list: ', bucket_list)\n",
    "        s.clear()\n",
    "        for x in bucket_list:   # 放回原序列\n",
    "            for y in x:\n",
    "                s.append(y)\n",
    "        i += 1\n",
    "\n",
    "radix_sort(disorder_list)\n",
    "print('after:',disorder_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 基数排序python实现: https://www.cnblogs.com/sfencs-hcy/p/10616446.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 对比"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 参考文献\n",
    "- 十大经典排序算法：https://www.cnblogs.com/itsharehome/p/11058010.html  \n",
    "- 十大经典排序算法（动图演示）：https://www.cnblogs.com/onepixel/articles/7674659.html\n",
    "- 排序算法总结：https://www.runoob.com/w3cnote/sort-algorithm-summary.html\n",
    "- 十大经典排序算法动画与解析，看我就够了！（配代码完全版）：https://www.cnblogs.com/fivestudy/p/10212306.html\n",
    "- 重磅|15种排序算法动画演示（附视频）：https://www.sohu.com/a/136042152_642762"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-07T04:39:06.629353Z",
     "iopub.status.busy": "2020-08-07T04:39:06.625527Z",
     "iopub.status.idle": "2020-08-07T04:39:06.646499Z",
     "shell.execute_reply": "2020-08-07T04:39:06.641469Z",
     "shell.execute_reply.started": "2020-08-07T04:39:06.629353Z"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-07T04:42:28.807404Z",
     "iopub.status.busy": "2020-08-07T04:42:28.806405Z",
     "iopub.status.idle": "2020-08-07T04:42:28.902716Z",
     "shell.execute_reply": "2020-08-07T04:42:28.896409Z",
     "shell.execute_reply.started": "2020-08-07T04:42:28.807404Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "1be780d03f7b4baf81dc8b9f4c5f91b9",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Canvas(toolbar=Toolbar(toolitems=[('Home', 'Reset original view', 'home', 'home'), ('Back', 'Back to previous …"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "ename": "AttributeError",
     "evalue": "'function' object has no attribute 'clear_output'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-69-f8ec8034b688>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     51\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     52\u001b[0m \u001b[0mplt\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 53\u001b[1;33m \u001b[0mdisplay\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mclear_output\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mwait\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mTrue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m: 'function' object has no attribute 'clear_output'"
     ]
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
